package medium;

import javafx.util.Pair;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/7/30 19:55
 */
public class No17_电话号码的字母组合 {
    public static void main(String[] args) {
        Solution17 solution17 = new Solution17();
        List<String> list = solution17.letterCombinations("5875");
        System.out.println();
    }
}

class Solution17 {
    Map<Character, String> map = initMap();
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.length() == 0) {
            return res;
        }
        //BFS
        //No.107.二叉树的层次遍历(参考)
        //根据分析,使用双端队列
        Deque<Pair<Character, Integer>> deque = new ArrayDeque<>();
        //最初的字母扔!
        String bigBase = map.get(digits.charAt(0)); //jkl
        for (int i = 0; i < bigBase.length(); i++) {
            deque.addLast(new Pair<>(bigBase.charAt(i), 0));
        }

        String add = "";
        while (!deque.isEmpty()) {
            Pair<Character, Integer> pair = deque.removeLast();
            //获取当前pop元素
            Character check = pair.getKey();
            Integer index = pair.getValue();
            
            //处理add,如何处理???
            //如果add长度跟index相同,则可以加 (找的规律)
            
            //这里用了很长时间分析,大家注意理解
            while (index < add.length()) {
                //add缩小
                add = add.substring(0, add.length() - 1);
            }
            
            add += check;
            index++;
            //下一级别
            //如果add 没有下一级别,则加
            if (index == digits.length()) {
                res.add(add);
            } else {
                //可以加,然后下一级别获取nextBase
                String nextBase = map.get(digits.charAt(index));
                for (int i = 0; i < nextBase.length(); i++) {
                    deque.addLast(new Pair<>(nextBase.charAt(i), index));
                }
            }
        }
        return res;
    }


    //数字转字母
    public Map<Character, String> initMap() {
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        return map;
    }
}



    //Map<Character, String> map = initMap();
    //public List<String> letterCombinations(String digits) {
    //    List<String> res = new ArrayList<>();
    //
    //    if (digits.length() == 0) {
    //        return res;            
    //    }
    //    letterCombinations(digits,0,"",res);
    //    return res;
    //    
    //}
    //
    ////回溯操作-map放全局
    //public void letterCombinations(String digits, int index,String add,List<String> res) {
    //    //当 letterCombinations(digits, ++index, add);递归到没有值的时候,加
    //    if (index == digits.length()) {
    //        res.add(add);
    //        return;
    //    }
    //    //要循环的按钮值 5->jkl
    //    String base = map.get(digits.charAt(index));//jkl
    //    
    //    //递归在这里进行
    //    for (int i = 0; i < base.length(); i++) {
    //        //每次递归会+add值
    //        add += base.charAt(i);
    //        //jtpj
    //        letterCombinations(digits, ++index, add,res);
    //        //这里注意回溯
    //        index--;
    //        add = add.substring(0, add.length() - 1);
    //    }
    //}
    //
    ////数字转字母
    //public Map<Character, String> initMap() {
    //    Map<Character, String> map = new HashMap<>();
    //    map.put('2', "abc");
    //    map.put('3', "def");
    //    map.put('4', "ghi");
    //    map.put('5', "jkl");
    //    map.put('6', "mno");
    //    map.put('7', "pqrs");
    //    map.put('8', "tuv");
    //    map.put('9', "wxyz");
    //    return map;
    //}



    //public List<String> letterCombinations(String digits) {
    //    //2-9
    //    //25 -> abc()  a
    //    //最最最最简单方法:强行穷举!!
    //    Map<Character, String> map = initMap();
    //    //获取输入的长度,根据长度穷举
    //    List<String> res = new ArrayList<>();
    //    int length = digits.length();
    //
    //    switch (length) {
    //        case 0:
    //            return res;
    //        case 1:
    //            //遍历map的value扔入res
    //            for (char a : map.get(digits.charAt(0)).toCharArray()) {
    //                //a:'j' 'k' 'l'
    //                String add = "";
    //                add += a;
    //                res.add(add);
    //            }
    //            return res;
    //        case 2:
    //            for (char a : map.get(digits.charAt(0)).toCharArray()) {
    //                for (char b : map.get(digits.charAt(1)).toCharArray()) {
    //                    //ab:'j''t' ....
    //                    String add = "";
    //                    add += a;
    //                    add += b;
    //                    res.add(add);
    //                }
    //            }
    //            return res;
    //        case 3:
    //            for (char a : map.get(digits.charAt(0)).toCharArray()) {
    //                for (char b : map.get(digits.charAt(1)).toCharArray()) {
    //                    for (char c : map.get(digits.charAt(2)).toCharArray()) {
    //                        //ab:'j''t' ....
    //                        String add = "";
    //                        add += a;
    //                        add += b;
    //                        add += c;
    //                        res.add(add);
    //                    }
    //                }
    //            }
    //            return res;
    //        case 4:
    //            for (char a : map.get(digits.charAt(0)).toCharArray()) {
    //                for (char b : map.get(digits.charAt(1)).toCharArray()) {
    //                    for (char c : map.get(digits.charAt(2)).toCharArray()) {
    //                        for (char d : map.get(digits.charAt(3)).toCharArray()) {
    //                            //ab:'j''t' ....
    //                            String add = "";
    //                            add += a;
    //                            add += b;
    //                            add += c;
    //                            add += d;
    //                            res.add(add);
    //                        }
    //                    }
    //                }
    //            }
    //            return res;
    //        default:
    //            return res;
    //    }
    //    
    //    
    //}
    //
    ////数字转字母
    //public Map<Character, String> initMap() {
    //    Map<Character, String> map = new HashMap<>();
    //    map.put('2', "abc");
    //    map.put('3', "def");
    //    map.put('4', "ghi");
    //    map.put('5', "jkl");
    //    map.put('6', "mno");
    //    map.put('7', "pqrs");
    //    map.put('8', "tuv");
    //    map.put('9', "wxyz");
    //    return map;
    //}






